package com.leetcode.partition9;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC802找到最终的安全状态 {
    
    public static List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length, m = 0, index = 0;
        for (int i = 0; i < n; i++) m += graph[i].length;
        int[] head = new int[n], element = new int[m], next = new int[m], inDegree = new int[n];
        for (int i = 0; i < n; i++) head[i] = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                //邻接表根据v不方便找到u，所以反向建图，结点graph[i][j]->i
                element[index] = i;
                next[index] = head[graph[i][j]];
                head[graph[i][j]] = index++;
                inDegree[i]++;
            }
        }
        //将所有入度为0的结点加入到队列中
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) queue.addLast(i);
        }
        List<Integer> answer = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            answer.add(u);
            for (int i = head[u]; i != -1; i = next[i]) {
                int v = element[i];
                inDegree[v]--;
                if (inDegree[v] == 0) queue.addLast(v);
            }
        }
        answer.sort((o1, o2) -> Integer.compare(o1, o2));
        return answer;
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
        System.out.println(eventualSafeNodes(graph));
    }
}
